<html>
<head><meta charset="utf-8"><title>Convert to SSA during llvm ir codegen · t-compiler/wg-llvm · Zulip Chat Archive</title></head>
<h2>Stream: <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/index.html">t-compiler/wg-llvm</a></h2>
<h3>Topic: <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/Convert.20to.20SSA.20during.20llvm.20ir.20codegen.html">Convert to SSA during llvm ir codegen</a></h3>

<hr>

<base href="https://rust-lang.zulipchat.com">

<head><link href="https://rust-lang.github.io/zulip_archive/style.css" rel="stylesheet"></head>

<a name="213904004"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/Convert%20to%20SSA%20during%20llvm%20ir%20codegen/near/213904004" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> bjorn3 <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/Convert.20to.20SSA.20during.20llvm.20ir.20codegen.html#213904004">(Oct 20 2020 at 11:20)</a>:</h4>
<p>I noticed that cg_llvm always uses <code>alloca</code> to store locals even when it is possible to use SSA values. This leads to more inefficient code and more ir to churn through for llvm. While llvm is able to turn it into SSA using the mem2reg pass, this doesn't happen for <code>-Copt-level=0</code>, which is the default. This means that cg_llvm generates slower code in debug mode than necessary. cg_clif is able to directly turn it into SSA form on the fly using cranelift_frontend, which uses an algorithm based on "Simple and Efficient Construction of Static Single Assignment Form" (<a href="https://github.com/bytecodealliance/wasmtime/blob/76998f0404d83f1c303887c5fd207e14a07dcf4c/cranelift/frontend/src/ssa.rs">cranelift source</a>)</p>
<div class="codehilite" data-code-language="Rust"><pre><span></span><code><span class="k">pub</span><span class="w"> </span><span class="k">fn</span> <span class="nf">a</span><span class="p">()</span><span class="w"> </span>-&gt; <span class="kt">u8</span> <span class="p">{</span><span class="w"></span>
<span class="w">    </span><span class="kd">let</span><span class="w"> </span><span class="k">mut</span><span class="w"> </span><span class="n">a</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="mi">0</span><span class="p">;</span><span class="w"></span>
<span class="w">    </span><span class="n">a</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="mi">1</span><span class="p">;</span><span class="w"></span>
<span class="w">    </span><span class="n">a</span><span class="w"></span>
<span class="p">}</span><span class="w"></span>
</code></pre></div>

<div class="codehilite" data-code-language="LLVM"><pre><span></span><code><span class="k">define</span> <span class="k">i8</span> <span class="vg">@_ZN7example1a17ha389e3fd0a4f8f11E</span><span class="p">()</span> <span class="k">unnamed_addr</span> <span class="vg">#0</span> <span class="p">{</span>
  <span class="nv">%a</span> <span class="p">=</span> <span class="k">alloca</span> <span class="k">i8</span><span class="p">,</span> <span class="k">align</span> <span class="m">1</span>
  <span class="k">store</span> <span class="k">i8</span> <span class="m">0</span><span class="p">,</span> <span class="k">i8</span><span class="p">*</span> <span class="nv">%a</span><span class="p">,</span> <span class="k">align</span> <span class="m">1</span>
  <span class="k">store</span> <span class="k">i8</span> <span class="m">1</span><span class="p">,</span> <span class="k">i8</span><span class="p">*</span> <span class="nv">%a</span><span class="p">,</span> <span class="k">align</span> <span class="m">1</span>
  <span class="nv nv-Anonymous">%0</span> <span class="p">=</span> <span class="k">load</span> <span class="k">i8</span><span class="p">,</span> <span class="k">i8</span><span class="p">*</span> <span class="nv">%a</span><span class="p">,</span> <span class="k">align</span> <span class="m">1</span>
  <span class="k">ret</span> <span class="k">i8</span> <span class="nv nv-Anonymous">%0</span>
<span class="p">}</span>
</code></pre></div>

<div class="codehilite"><pre><span></span><code>function u0:0() -&gt; i8 system_v {
                                block0:
                                    nop
                                    jump block1

                                block1:
                                    nop
@0001                               v0 = iconst.i8 0
@0002                               v1 = iconst.i8 1
@0003                               v2 = iconst.i8 1
@0005                               return v2
}
</code></pre></div>


<p>As for the speed difference. Look at this:</p>
<div class="codehilite"><pre><span></span><code>$ ./raytracer_cg_clif
10519 milliseconds elapsed.
$ ./raytracer_cg_clif_no_ssa
19927 milliseconds elapsed.
</code></pre></div>


<p>This is both with the same sysroot compiled with SSA conversion.</p>



<a name="213904184"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/Convert%20to%20SSA%20during%20llvm%20ir%20codegen/near/213904184" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> bjorn3 <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/Convert.20to.20SSA.20during.20llvm.20ir.20codegen.html#213904184">(Oct 20 2020 at 11:23)</a>:</h4>
<p>To be fair it seems that cg_llvm does perform this in limited cases where there is only a single assignment and some other conditions.</p>



<a name="213904502"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/Convert%20to%20SSA%20during%20llvm%20ir%20codegen/near/213904502" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> bjorn3 <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/Convert.20to.20SSA.20during.20llvm.20ir.20codegen.html#213904502">(Oct 20 2020 at 11:27)</a>:</h4>
<p>For reference this is the cg_clif diff I used to test this:</p>
<div class="codehilite" data-code-language="Diff"><pre><span></span><code><span class="gh">diff --git a/src/analyze.rs b/src/analyze.rs</span>
<span class="gh">index fd25b19..ae497f9 100644</span>
<span class="gd">--- a/src/analyze.rs</span>
<span class="gi">+++ b/src/analyze.rs</span>
<span class="gu">@@ -19,7 +19,7 @@ pub(crate) fn analyze(fx: &amp;FunctionCx&lt;'_, '_, impl Module&gt;) -&gt; IndexVec&lt;Local, S</span>
         .map(|local_decl| {
             let ty = fx.monomorphize(&amp;local_decl.ty);
             if fx.clif_type(ty).is_some() || fx.clif_pair_type(ty).is_some() {
<span class="gd">-                SsaKind::Ssa</span>
<span class="gi">+                SsaKind::NotSsa</span>
             } else {
                 SsaKind::NotSsa
             }
</code></pre></div>



<a name="213931068"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/Convert%20to%20SSA%20during%20llvm%20ir%20codegen/near/213931068" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> cuviper <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/Convert.20to.20SSA.20during.20llvm.20ir.20codegen.html#213931068">(Oct 20 2020 at 14:55)</a>:</h4>
<p>What's the effect on debuginfo?</p>



<a name="213943913"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/Convert%20to%20SSA%20during%20llvm%20ir%20codegen/near/213943913" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Josh Triplett <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/Convert.20to.20SSA.20during.20llvm.20ir.20codegen.html#213943913">(Oct 20 2020 at 16:26)</a>:</h4>
<p><span class="user-mention" data-user-id="133247">@bjorn3</span> How easily could cg_llvm use SSA directly in cases where it currently uses alloca?</p>



<a name="213945176"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/Convert%20to%20SSA%20during%20llvm%20ir%20codegen/near/213945176" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> bjorn3 <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/Convert.20to.20SSA.20during.20llvm.20ir.20codegen.html#213945176">(Oct 20 2020 at 16:35)</a>:</h4>
<p><span class="user-mention silent" data-user-id="138448">cuviper</span> <a href="#narrow/stream/187780-t-compiler.2Fwg-llvm/topic/Convert.20to.20SSA.20during.20llvm.20ir.20codegen/near/213931068">said</a>:</p>
<blockquote>
<p>What's the effect on debuginfo?</p>
</blockquote>
<p>The same as the current limited SSA conversion. <a href="https://github.com/rust-lang/rust/blob/59dafb876e125c49fca93820c5ef22da3fcb8644/compiler/rustc_codegen_ssa/src/mir/debuginfo.rs#L228">https://github.com/rust-lang/rust/blob/59dafb876e125c49fca93820c5ef22da3fcb8644/compiler/rustc_codegen_ssa/src/mir/debuginfo.rs#L228</a></p>
<blockquote>
<p>"Spill" the value onto the stack, for debuginfo,<br>
without forcing non-debuginfo uses of the local<br>
to also load from the stack every single time.<br>
FIXME(<a href="https://github.com/rust-lang/rust/issues/68817">#68817</a>) use <code>llvm.dbg.value</code> instead,<br>
at least for the cases which LLVM handles correctly.</p>
</blockquote>
<p><span class="user-mention silent" data-user-id="239881">Josh Triplett</span> <a href="#narrow/stream/187780-t-compiler.2Fwg-llvm/topic/Convert.20to.20SSA.20during.20llvm.20ir.20codegen/near/213943913">said</a>:</p>
<blockquote>
<p><span class="user-mention silent" data-user-id="133247">bjorn3</span> How easily could cg_llvm use SSA directly in cases where it currently uses alloca?</p>
</blockquote>
<p>It would need an implementation of "Simple and Efficient Construction of Static Single Assignment Form" or another algorithm for constructing SSA form. It is not trivial but it is relatively small. The Cranelift implementation is 700 lines including a lot of comments and excluding tests.</p>



<a name="213956159"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/Convert%20to%20SSA%20during%20llvm%20ir%20codegen/near/213956159" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jubilee <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/Convert.20to.20SSA.20during.20llvm.20ir.20codegen.html#213956159">(Oct 20 2020 at 17:54)</a>:</h4>
<p>It sounds like that would be shared code between cg_clif and cg_llvm, can they share some of that?</p>



<a name="213956377"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/Convert%20to%20SSA%20during%20llvm%20ir%20codegen/near/213956377" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> bjorn3 <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/Convert.20to.20SSA.20during.20llvm.20ir.20codegen.html#213956377">(Oct 20 2020 at 17:55)</a>:</h4>
<p>The Cranelift implementation only works for clif ir. It should be possible to be generic over the ir though.</p>



<a name="213956742"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/Convert%20to%20SSA%20during%20llvm%20ir%20codegen/near/213956742" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jubilee <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/Convert.20to.20SSA.20during.20llvm.20ir.20codegen.html#213956742">(Oct 20 2020 at 17:58)</a>:</h4>
<p>Can you link the Cranelift implementation?</p>



<a name="213956899"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/Convert%20to%20SSA%20during%20llvm%20ir%20codegen/near/213956899" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> bjorn3 <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/Convert.20to.20SSA.20during.20llvm.20ir.20codegen.html#213956899">(Oct 20 2020 at 17:59)</a>:</h4>
<p><a href="https://github.com/bytecodealliance/wasmtime/blob/76998f0404d83f1c303887c5fd207e14a07dcf4c/cranelift/frontend/src/ssa.rs">https://github.com/bytecodealliance/wasmtime/blob/76998f0404d83f1c303887c5fd207e14a07dcf4c/cranelift/frontend/src/ssa.rs</a></p>



<a name="213957802"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/Convert%20to%20SSA%20during%20llvm%20ir%20codegen/near/213957802" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jubilee <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/Convert.20to.20SSA.20during.20llvm.20ir.20codegen.html#213957802">(Oct 20 2020 at 18:05)</a>:</h4>
<p>So one could pull something like that into cg_ssa.</p>



<a name="213963226"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/Convert%20to%20SSA%20during%20llvm%20ir%20codegen/near/213963226" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jubilee <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/Convert.20to.20SSA.20during.20llvm.20ir.20codegen.html#213963226">(Oct 20 2020 at 18:48)</a>:</h4>
<p>There have also been mentions of forming a fully SSA data structure from MIR so as to do a proper optimization pass, since MIR is not really designed to do optimization.</p>
<p><span class="user-mention silent" data-user-id="125250">Wesley Wiser</span> <a href="#narrow/stream/189540-t-compiler.2Fwg-mir-opt/topic/peephole.20optimization/near/211688371">said</a>:</p>
<blockquote>
<p>We've talked a little before about having a different IR for optimizations. MIR was not really designed to be optimization friendly, it was really just more concerned with being nice to consume from the borrow checker (iirc).</p>
</blockquote>
<p><span class="user-mention silent" data-user-id="220917">Nick Fitzgerald</span> <a href="#narrow/stream/189540-t-compiler.2Fwg-mir-opt/topic/peephole.20optimization/near/211688766">said</a>:</p>
<blockquote>
<p>yeah, SSA would make this a lot easier</p>
</blockquote>
<p>So it seems like this is generally considered a good idea.</p>



<a name="213970939"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/Convert%20to%20SSA%20during%20llvm%20ir%20codegen/near/213970939" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> bjorn3 <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/Convert.20to.20SSA.20during.20llvm.20ir.20codegen.html#213970939">(Oct 20 2020 at 19:51)</a>:</h4>
<p>cc <a href="https://bytecodealliance.zulipchat.com/#narrow/stream/217117-cranelift/topic/ir.20independent.20implementation.20of.20ssa.20conversion/near/213970608">https://bytecodealliance.zulipchat.com/#narrow/stream/217117-cranelift/topic/ir.20independent.20implementation.20of.20ssa.20conversion/near/213970608</a></p>



<hr><p>Last updated: Aug 07 2021 at 22:04 UTC</p>
</html>